package ToYesterday.matixRoute12;

import org.junit.Test;

import java.util.Stack;

public class Solution {
    boolean find = false;
    boolean fail = false;
    char [][] maze = {
            {'c','c','c','b','b'},
            {'a','a','b','a','b'},
            {'c','c','c','a','a'},
            {'b','a','c','a','a'},
            {'a','a','b','a','b'},
            {'c','b','a','a','a'},
            {'c','b','a','c','c'},
            {'b','a','a','a','c'},
            {'c','c','b','a','b'},
            {'a','b','b','a','b'},
            {'c','b','c','a','b'},
            {'b','a','a','c','b'}
    };
    boolean [][] mazeMock = new boolean[maze.length][maze[0].length];
    Stack<Character> stack = new Stack<>();
    char [] str ;
    String strin = "ccbcccbcaaaab";
    @Test
    public void solution(){
        str = strin.toCharArray();
        findStr(maze,0,0,str ,0);
        if (stack.empty()) System.out.println("查找失败");
        else System.out.println("查找成功");
    }

    public void findStr(char[][] chars,int i,int j ,char [] str,int k){
        if (i<chars.length && j<chars[0].length && chars[i][j] == str[k] && find == false && mazeMock[i][j] == false){
            stack.push(chars[i][j]);
            mazeMock[i][j] = true;
            if (k == (str.length-1)) {
                if (stack.size() == str.length) {
                    find = true;
                    return;
                }
            }
            if (numMeaning(j+1,0,chars[0].length) && !find && !fail){
                findStr(chars,i,j+1,str,k+1);
            }
            if (numMeaning(i+1,0,chars.length)&& !find && !fail){
                findStr(chars,i+1,j,str,k+1);
            }
            if (numMeaning(j-1,0,chars[0].length)  &&(j-1 >=0 )&& !find && !fail){
                findStr(chars,i,j-1,str,k+1);
            }
            if (numMeaning(i-1,0,chars.length) && (i-1>=0)&& !find && !fail){
                findStr(chars,i-1,j,str,k+1);
            }
            if (!find) {
                stack.pop();
                mazeMock[i][j] = false;
                if (stack.empty() && i<chars.length && j<chars[0].length){
                    findStr(chars,i,j+1,str,k);
//                    if (i<chars.length && find == false && fail == false) j=0;
//                    if (fail == false && find == false) findStr(chars,i+1,j,str,k);
                }
            }
            else return;
        } else {
            if (stack.empty() && i<chars.length && j<chars[0].length){
                if (i == (chars.length-1) && (j == chars[0].length-1) && chars[i][j]!= str[str.length-1]){
                    fail = true;
                    return;
                }
                if (fail == false && find == false) findStr(chars,i,j+1,str,k);
                if (i<chars.length && find == false && fail == false) j=0;
                if (fail == false && find == false) findStr(chars,i+1,j,str,k);
            }
            return;
        }
    }
    public boolean numMeaning(int i, int start, int stop){
        return i>=start && i< stop;
    }

}
